其实只有 $21$ 道题。两道不是网络流，另一道是假题。

一.最大流问题

简单题

1.P2756 飞行员配对方案问题

经典的二分图最大匹配。

建立源点与汇点，分别向二分图的其中一部分连容量为 $1$ 的边。

可匹配的点之间也连一条边，容量随意。

最后跑最大流即可。

方案可以根据残余网络构造出来。

2.P3254 圆桌问题

3.P2763 试题库问题

中等题

4.P2764 最小路径覆盖问题

首先每个点用一条边覆盖，为了使路径尽可能少，我们要连接一些路径。

将每个点拆成两个点 $x_i,y_i$ ，对于 $u \rightarrow v$ 这条边，连接 $x_u,y_v$ 并将容量设为 $1$，如果这条边有流则表示将 $u,v$ 的路径合并。

然后连接 $S \rightarrow x_i,y_i\rightarrow T$，容量也设为 $1$ （要求顶点不相交，每个点只能连接一次）

最后图的最大流便是连接的最大数量，答案为 $n-\text{最大流}$。

方案直接记录后继节点就可以了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 300 , MAXM = 7000;
struct node {
	int v , flow , nxt;
}Graph[ 2 * MAXM + 5 ];
int tot = 1 , Head[ MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
	Graph[ ++ tot ] = { v , f , Head[ u ] };
	Head[ u ] = tot;
}

int n , m , s , t;
int lev[ MAXN + 5 ] , cur[ MAXN + 5 ] , nxt[ MAXN + 5 ] , sta[ MAXN + 5 ];
bool Layering( int s , int t ) {
    memset( lev , -1 , sizeof( lev ) );
	memcpy( cur , Head , sizeof( Head ) );
    queue< int > Que;
    Que.push( s ) , lev[ s ] = 0;
    while( !Que.empty( ) ) {
        int u = Que.front( ); Que.pop( );
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flow;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ t ] != -1;
}

int dfs( int u , int t , int f ) {
	if( u == t ) return f;
	for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
		int v = Graph[ i ].v , flw = Graph[ i ].flow;
		cur[ u ] = i;
		if( flw > 0 && lev[ u ] < lev[ v ] ) {
			int mf = dfs( v , t , min( f , flw ) );
			if( mf ) {
				Graph[ i ].flow -= mf; Graph[ i ^ 1 ].flow += mf;
				if( u != s && v > n ) sta[ v - n ] = 1;
				nxt[ u ] = v;
				return mf;
			}
		}
	}
	return 0;
}

int Dinic( int s , int t ) {
	int Maxf = 0;
	while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
	for( int i = 1 ; i <= n ; i ++ )
		if( !sta[ i ] ) {
			printf("%d", i );
			int u = i;
			while( nxt[ u ] && nxt[ u ] != t ) {
				printf(" %d", nxt[ u ] - n );
				u = nxt[ u ] - n;
			}
			printf("\n");
		}
	return Maxf;
}

int main( ) {
	scanf("%d %d",&n,&m);
	s = 2 * n + 1 , t = 2 * n + 2;
	for( int i = 1 , u , v ; i <= m ; i ++ ) {
		scanf("%d %d",&u,&v);
		Add_Edge( u , v + n , 1 );
		Add_Edge( v + n , u , 0 );
	}
	for( int i = 1 ; i <= n ; i ++ )
		Add_Edge( s , i , 1 ) , Add_Edge( i , s , 0 );
	for( int i = 1 ; i <= n ; i ++ )
		Add_Edge( i + n , t , 1 ) , Add_Edge( t , i + n , 0 );
    
	
	printf("%d\n", n - Dinic( s , t ) );
	return 0; 
} 

变式：P5769 [JSOI2016]飞机调度 题解

5.P2774 方格取数问题

选出的格子不能相邻，这是此题的关键。

如果两个格子相邻，那么它们坐标和的奇偶性一定不同。

将限制条件看成一条边，那么图是一个二分图。分别从源点和汇点向两部分连边，容量即为格子里的数。

不选格子里的数相当删去于将源点/汇点与该点的边。

求出图的最小割即可。

因为不能改变限制条件，所以二分图内部的容量设为极大值。

注意不要重复建边。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 10000 , MAXM = 6 * MAXN;
struct Edge {
    int v , flw , nxt;
    Edge(){}
    Edge( int V , int Flw , int Nxt ) { v = V , flw = Flw , nxt = Nxt; }
}Graph[ MAXM + 5 ];
int Head[ MAXN + 5 ] , Enum = 1;
void Add_Edge( int u , int v , int flw ) {
    Graph[ ++ Enum ] = Edge( v , flw , Head[ u ] ); Head[ u ] = Enum;
    Graph[ ++ Enum ] = Edge( u , 0   , Head[ v ] ); Head[ v ] = Enum;
}

int cur[ MAXN + 5 ] , lev[ MAXN + 5 ];
bool Layer( int S , int T ) {
    memcpy( cur , Head , sizeof( Head ) );
    memset( lev , -1 , sizeof( lev ) );
    queue< int > Que;
    lev[ S ] = 0 , Que.push( S );
    while( !Que.empty() ) {
        int u = Que.front(); Que.pop();
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flw;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ T ] != -1;
}
int dfs( int u , int t , int f ) {
    if( u == t ) return f;
    for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
        int v = Graph[ i ].v , flw = Graph[ i ].flw ;
        cur[ u ] = i;
        if( flw > 0 && lev[ u ] < lev[ v ] ) {
            int d = dfs( v , t , min( f , flw ) );
            if( d > 0 ) {
                Graph[ i ].flw -= d , Graph[ i ^ 1 ].flw += d;
                return d;
            }
        }
    }
    return 0;
}
int Dinic( int S , int T ) {
    int Mxf = 0;
    while( Layer( S , T ) ) for( int fl = 0 ; ( fl = dfs( S , T , Inf ) ) > 0 ; Mxf += fl );
    return Mxf;
}

int n , m , a[ 105 ][ 105 ] , Suma , S , T;
int hs( int x , int y ) { return ( x - 1 ) * 100 + y; }
int main( ) {
	scanf("%d %d",&n,&m); S = hs( n + 1 , 1 ) , T = hs( n + 1 , 2 );
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= m ; j ++ )
			scanf("%d",&a[ i ][ j ]) , Suma += a[ i ][ j ];
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= m ; j ++ )
			if( ( i + j ) & 1 ) Add_Edge( S , hs( i , j ) , a[ i ][ j ] );
			else Add_Edge( hs( i , j ) , T , a[ i ][ j ] );
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= m ; j ++ )
			if( ( i + j ) & 1 ) {
				if( i != 1 ) Add_Edge( hs( i , j ) , hs( i - 1 , j ) , Inf );
				if( i != n ) Add_Edge( hs( i , j ) , hs( i + 1 , j ) , Inf );
				if( j != 1 ) Add_Edge( hs( i , j ) , hs( i , j - 1 ) , Inf );
				if( j != m ) Add_Edge( hs( i , j ) , hs( i , j + 1 ) , Inf );
			}
	printf("%d\n", Suma - Dinic( S , T ) );
    return 0;
}

6.P2766 最长不下降子序列问题

首先可以 $\mathcal O(n^2)$ dp 求得以 $i$ 结尾的最长不下降子序列。

第一问的答案 $s=\max\{dp_i\}$。

然后源点向所有 $dp_i=1$ 的点连容量为 $1$ 的边，汇点向所有 $dp_i=s$ 的点连容量为 $1$ 的边。

那么 dp 转移可以这样刻画：

对于 $j<i,a_j \le a_i,dp_i=dp_j+1$ 的 $i,j$ ，在它们之间连一条容量为 $1$ 的边。

这样不能保证每个点只被选 $1$ 次，所以将每个点拆成两个点即可。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 1000 , MAXM = MAXN * ( MAXN + 2 );
struct Edge {
    int v , flw , nxt;
    Edge(){}
    Edge( int V , int Flw , int Nxt ) { v = V , flw = Flw , nxt = Nxt; }
}Graph[ MAXM + 5 ];
int Head[ MAXN + 5 ] , Enum = 1;
void Add_Edge( int u , int v , int flw ) {
    Graph[ ++ Enum ] = Edge( v , flw , Head[ u ] ); Head[ u ] = Enum;
    Graph[ ++ Enum ] = Edge( u , 0   , Head[ v ] ); Head[ v ] = Enum;
}

int cur[ MAXN + 5 ] , lev[ MAXN + 5 ];
bool Layer( int S , int T ) {
    memcpy( cur , Head , sizeof( Head ) );
    memset( lev , -1 , sizeof( lev ) );
    queue< int > Que;
    lev[ S ] = 0 , Que.push( S );
    while( !Que.empty() ) {
        int u = Que.front(); Que.pop();
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flw;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ T ] != -1;
}
int dfs( int u , int t , int f ) {
    if( u == t ) return f;
    for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
        int v = Graph[ i ].v , flw = Graph[ i ].flw ;
        cur[ u ] = i;
        if( flw > 0 && lev[ u ] < lev[ v ] ) {
            int d = dfs( v , t , min( f , flw ) );
            if( d > 0 ) {
                Graph[ i ].flw -= d , Graph[ i ^ 1 ].flw += d;
                return d;
            }
        }
    }
    return 0;
}
int Dinic( int S , int T ) {
    int Mxf = 0;
    while( Layer( S , T ) ) for( int fl = 0 ; ( fl = dfs( S , T , Inf ) ) > 0 ; Mxf += fl );
    return Mxf;
}

int n , a[ MAXN + 5 ] , S , T;
int s , dp[ MAXN + 5 ];

int main( ) {
	scanf("%d",&n); S = 2 * n + 1 , T = S + 1;
	for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[ i ]);
	
	if( n == 1 ) return printf("%d\n%d\n%d\n",1,1,1) & 0; 
	
	for( int i = 1 ; i <= n ; i ++ ) {
		dp[ i ] = 1;
		for( int j = 1 ; j < i ; j ++ )
			if( a[ j ] <= a[ i ] ) dp[ i ] = max( dp[ i ] , dp[ j ] + 1 );
		s = max( s , dp[ i ] );
	}
	printf("%d\n", s );
	
	for( int i = 1 ; i <= n ; i ++ ) {
		if( dp[ i ] == 1 ) Add_Edge( S , i , 1 );
		if( dp[ i ] == s ) Add_Edge( n + i , T , 1 );
	}
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j < i ; j ++ )
			if( a[ j ] <= a[ i ] && dp[ i ] == dp[ j ] + 1 ) Add_Edge( j + n , i , 1 );
	for( int i = 1 ; i <= n ; i ++ ) Add_Edge( i , n + i , 1 );
	printf("%d\n", Dinic( S , T ) );
	
	memset( Head , 0 , sizeof( Head ) ); Enum = 1;
	for( int i = 1 ; i <= n ; i ++ ) {
		if( dp[ i ] == 1 ) Add_Edge( S , i , i == 1 ? Inf : 1 );
		if( dp[ i ] == s ) Add_Edge( n + i , T , i == n ? Inf : 1 );
	}
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j < i ; j ++ )
			if( a[ j ] <= a[ i ] && dp[ i ] == dp[ j ] + 1 ) Add_Edge( j + n , i , 1 );
	for( int i = 1 ; i <= n ; i ++ ) Add_Edge( i , n + i , ( i == 1 || i == n ) ? Inf : 1 );
	printf("%d\n", Dinic( S , T ) );
    return 0;
}

进阶题

7.P2765 魔术球问题

考虑将两个能放在一起的球之间连一条边，因为要求球要依次放，所以边由编号较小的球连向编号较大的。

那么一个柱子可看作有向图上的一条简单路径。

原问题即转化为 $n$ 条不相交的简单路径最多能覆盖多少点。

很像第 $4$ 题，枚举答案可以发现前几项：

$1,3,7,11,17.23$

作差得到：

$2,4,4,6,6$

那么可以先算出球数，然后用第四题的方法构造答案即可。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 3200 , MAXM = MAXN * ( MAXN + 2 );
struct node { int v , flw , nxt; }Graph[ 2 * MAXM + 5 ];
int Enum = 1 , Head[ MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
	Graph[ ++ Enum ] = { v , f , Head[ u ] }; Head[ u ] = Enum;
	Graph[ ++ Enum ] = { u , 0 , Head[ v ] }; Head[ v ] = Enum;
}

int n , k , S , T;
int lev[ MAXN + 5 ] , cur[ MAXN + 5 ] , nxt[ MAXN + 5 ] , sta[ MAXN + 5 ];
bool Layering( int s , int t ) {
    memset( lev , -1 , sizeof( lev ) );
	memcpy( cur , Head , sizeof( Head ) );
    queue< int > Que;
    Que.push( s ) , lev[ s ] = 0;
    while( !Que.empty( ) ) {
        int u = Que.front( ); Que.pop( );
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flw;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ t ] != -1;
}
int dfs( int u , int t , int f ) {
	if( u == t ) return f;
	for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
		int v = Graph[ i ].v , flw = Graph[ i ].flw;
		cur[ u ] = i;
		if( flw > 0 && lev[ u ] < lev[ v ] ) {
			int mf = dfs( v , t , min( f , flw ) );
			if( mf ) {
				Graph[ i ].flw -= mf; Graph[ i ^ 1 ].flw += mf;
				if( u != S && v > n ) sta[ v - n ] = 1;
				nxt[ u ] = v;
				return mf;
			}
		}
	}
	return 0;
}
int Dinic( int s , int t ) {
	int Maxf = 0;
	while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
	for( int i = 1 ; i <= n ; i ++ )
		if( !sta[ i ] ) {
			printf("%d", i );
			int u = i;
			for( int u = i ; nxt[ u ] && nxt[ u ] != t ; u = nxt[ u ] - n ) printf(" %d", nxt[ u ] - n );
			printf("\n");
		}
	return Maxf;
}

bool sqt[ MAXN * MAXN + 5 ];
int main( ) {
	scanf("%d",&k); n = ( k * ( k + 2 ) + ( k & 1 ) - 2 ) / 2;
	printf("%d\n", n );
	
	S = 2 * n + 1 , T = S + 1;
	for( int i = 1 ; i <= n ; i ++ ) sqt[ i * i ] = 1;
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = i + 1 ; j <= n ; j ++ )
			if( sqt[ i + j ] ) Add_Edge( i , n + j , 1 );
	for( int i = 1 ; i <= n ; i ++ ) Add_Edge( S , i , 1 );
	for( int i = 1 ; i <= n ; i ++ ) Add_Edge( n + i , T , 1 );
	Dinic( S , T );
	return 0; 
} 

• P2762 太空飞行计划问题
• P2754 [CTSC1999]家园 / 星际转移问题

二.费用流问题

• P4016 负载平衡问题

• P3358 最长k可重区间集问题

• P3358 最长k可重区间集问题

• P2770 航空路线问题

• P4009 汽车加油行驶问题

• P4015 运输问题

• P4012 深海机器人问题

• P4013 数字梯形问题

• P1251 餐巾计划问题

• P3355 骑士共存问题

• P3357 最长k可重线段集问题

• P3356 火星探险问题